package com.leecode;

/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 * <p>
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * <p>
 * 你的算法时间复杂度必须是 O(log n) 级别。
 * <p>
 * 如果数组中不存在目标值，返回 [-1, -1]。
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: [3,4]
 */
public class Leet34 {
	public static void main(String[] args) {
		new Leet34().searchRange2(new int[]{5, 7, 7, 8, 8, 10}, 8);
//		new Leet34().searchRange(new int[]{1,3}, 1);
//		new Leet34().searchRange(new int[]{0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 8, 10, 10}, 4);
	}

	public int[] searchRange(int[] nums, int target) {
		int[] res = new int[]{-1, -1};
		if (nums.length == 1) {//不写就bug
			if (nums[0] != target) return res;
			return new int[]{0, 0};
		}
		recur(nums, 0, nums.length - 1, target, res, null);
		return res;
	}

	/**
	 * 100%,54%,我
	 * 100%,85%,赞最多的,独立一个二分方法,调二分方法两次分别救出left,righ,
	 * @param zeroOrOne null代表更新两侧,0代表更新左侧,1代表右侧
	 */
	public void recur(int[] nums, int b, int e, int tar, int[] res, Integer zeroOrOne) {
		int length = e - b + 1;
		if (length <= 0) return;//doNothing
		if (length == 1) {
			if (nums[e] == tar) {
				if (zeroOrOne != null) {
					res[zeroOrOne] = e;//自己都觉得这个zOO很灵性
				} else {
					res[0] = e;
					res[1] = e;
				}
			}
			return;//没有会bug
		}
		if (tar < nums[b] || tar > nums[e]) return;//超纲了,doNothing

		int middleIndex = (e + b + 1) / 2;//e-b+1是bug
		int middle = nums[middleIndex];

		if (middle == tar) {
			if (zeroOrOne == null) {//null代表更新两侧,0代表更新左侧,1代表右侧
				res[0] = middleIndex;
				res[1] = middleIndex;
			} else {
				res[zeroOrOne] = middleIndex;
			}
			if (zeroOrOne == null) {
				recur(nums, b, middleIndex - 1, tar, res, 0);
				recur(nums, middleIndex + 1, e, tar, res, 1);

			} else if (zeroOrOne == 0) {
				recur(nums, b, middleIndex - 1, tar, res, 0);

			} else if (zeroOrOne == 1) {
				recur(nums, middleIndex + 1, e, tar, res, 1);

			}
		} else if (tar < middle) {
			recur(nums, b, middleIndex - 1, tar, res, zeroOrOne);
		} else if (middle < tar) {
			recur(nums, middleIndex + 1, e, tar, res, zeroOrOne);
		}

		// return res;
	}

	/**
	 * 100%,92%
	 * 考点:要求logn,一看就是二分,重点在于:二分主体能否处理好"特殊情况",如何优雅写"主体逻辑"
	 */
	public int[] searchRange2(int[] nums, int target) {
		int[] res = new int[]{-1, -1};
		if (nums == null || nums.length == 0) return res;
		if (target < nums[0] || target > nums[nums.length - 1]) return res;//理论上讲,边界写到这就结束了,剩下的就是二分主体能否处理好"特殊情况"

		int b = 0;
		int e = nums.length - 1;
		while (b <= e) {//bug:没有=,典例:len为1,返回错误
			int m = (b + e) / 2;
			if (nums[m] == target) {
				if (m == 0 || nums[m - 1] != target) {
					res[0] = m;
					break;
				} else {
					e = m - 1;
				}
			} else if (nums[m] < target) {
				b = m + 1;
			} else {
				e = m - 1;
			}
		}
		b = 0;
		e = nums.length - 1;
		while (b <= e) {
			int m = (b + e) / 2;
			if (nums[m] == target) {
				if (m == nums.length - 1 || nums[m + 1] != target) {
					res[1] = m;
					break;
				} else {
					b = m + 1;
				}
			} else if (nums[m] < target) {
				b = m + 1;
			} else {
				e = m - 1;
			}
		}
		return res;
	}
}
